\section{同余类环 $\symbb{Z}/m\symbb{Z}$ 中的单位}

\begin{frame}{环$\symbb{Z}/m\symbb{Z}$ 中的单位}

  \pause
  设 $R$ 为含么交换环， $R$ 中元素 $\alpha$ 称为 (乘法) \emph{可逆}的， 是指存在 $\alpha^{\prime} \in R$ 使 $\alpha^{\prime} \alpha=1$ (此 $\alpha^{\prime}$ 称为 $\alpha$ 的 (乘法) \emph{逆}， 记为 $\alpha^{-1}$). 
\pause
  $\alpha$ 的逆是唯一的{\verify}。
%， 因若 $\alpha^{\prime} \alpha=1=$ $\alpha^{\prime \prime} \alpha$, 则
%\[
%\alpha^{\prime}\left(\alpha \alpha^{\prime}\right)=\alpha^{\prime \prime}\left(\alpha \alpha^{\prime}\right)
%\]
%故 $\alpha^{\prime}=\alpha^{\prime \prime}$. 
  \pause
环 $R$ 中的可逆元也称为其\emph{单位} (unit), 单位全体记为 $R^{*}$.
(实际上$R^*$构成群。)

\pause
特别， 对于模 $m$ 同余类环 $\mathbb{Z} / m \mathbb{Z}$, 其中元素 $\bar{a}$ 可逆相当于存在 $\overline{a^{\prime}} \in \mathbb{Z} / m \mathbb{Z}$使得
\[
\overline{a^{\prime}} \cdot \bar{a}=\overline{1}\quad \text { (此 $\overline{a^{\prime}}$ 称为 $\bar{a}$  的逆， 记为  $\bar{a}^{-1}$); }
\]
\pause
也称 $a$ 模 $m$ 可逆， 因为 $\overline{a^{\prime}} \cdot \bar{a}=\overline{1}$ 相当于
\[
  a^{\prime} \cdot a \equiv 1 \quad(\mod m).
\]
\pause
$\mathbb{Z} / m \mathbb{Z}$ 中的可逆元全体记为 $(\mathbb{Z} / m \mathbb{Z})^*$ 或 $U_{m}$.

\pause
\begin{theorem}%定理1
(1) $\bar{a} \in \mathbb{Z} / m \mathbb{Z}$ 可逆当且仅当 $(a, m)=1$. 故 $\mathbb{Z} / m \mathbb{Z}$ 中的(乘法)可逆元集恰为“小于 $m$ 且与 $m$ 互素的正整数所代表的同余类集”，即
\[
  U_{m}=(\mathbb{Z} / m \mathbb{Z})^{*}=\{\bar{a} \mid(a, m)=1,1 \leqslant a<m\}.
\]

 (2) 若 $m=p$ 为素数， 则 $\mathbb{Z} / p \mathbb{Z}$ 中的非零元均可逆， 从而 $\mathbb{Z} / p \mathbb{Z}$ 为域， 记为
 \[
   \mathbb{F}_{p}=\mathbb{Z} / p \mathbb{Z}=\{\overline{0}, \overline{1}, \cdots, \overline{p-1}\}.
 \]

 (3) 若 $m$ 不是素数， $\mathbb{Z} / m \mathbb{Z}$ 不是域。实际上，有整数 $1<b<m$ 使 $(b, m)=d>1$, 于是 $\bar{b} \in \mathbb{Z} / m \mathbb{Z}$ 是零因子， 不可逆。 
 \end{theorem}
 \end{frame}

 \begin{frame}
   \begin{proof}
    (1) (i) 若 $(a, m)=1$, 则由 Bézout 等式知有整数 $u, v$ 使 $u a+v m=1$.模 $m$ 得
  \[
  \overline{u a+v m}=\overline{1},
\]
即 $\bar{u} \bar{a}+\bar{v} \bar{m}=\overline{1}$, 故 $\bar{u} \bar{a}=\overline{1}$. 这说明 $\bar{a}$ 可逆， 且 $\bar{u}$ 为其逆。

(ii) 若 $(b, m)=d>1$, 则 $m=m_{1} d, b=b_{1} d$, 故
\[
  b \cdot m_{1}=b_{1} d m_{1}=b_{1} m \equiv 0 \quad(\mod m),
\]
即 $\bar{b} \cdot \overline{m_{1}}=\overline{0}$, 故 $\bar{b}$ 是零因子。 进而可知， $\bar{b}$ 不可逆：假若 $\bar{b}$ 有逆元 $\bar{b}^{-1} \in \mathbb{Z} / m \mathbb{Z}$,
将上式两边同乘 $\bar{b}^{-1}$, 得到 $\overline{m_{1}}=\overline{0}$, 矛盾。

 (2) 因 $m=p$ 为素数， 故 $1,2, \cdots, p-1$ 均与 $p$ 互素， 从而 $\overline{1}, \overline{2}, \cdots$, $\overline{p-1}$ 均可逆。

  (3) 此时有 $b$ 使 $(b, m)=d>1$, 由 (1) (ii) 知 $\bar{b}$ 不可逆。
\end{proof}

\pause
\begin{remark}%注记1
上述证明也给出了求逆的方法：辗转相除求 Bézout 等式 $u a+v m=$ 1 , 则 $\bar{u}$ 为 $\bar{a}$ 的逆。
\end{remark}

\pause
\begin{remark}%注记2
当 $(b, m)=d>1$ 时， 上述得到
$
\bar{b} \cdot \overline{m_{1}}=\overline{0}.
$
也就是说， $b$ 与 $m_{1}=\frac{m}{d}$ 是模 $m$ 的零因子配对。 $b$ 在 $m$ 中的因子补集是 $\frac{m}{d}$. 例如，模 $8=2 \cdot 2 \cdot 2$ 时， $6=2 \cdot 3$ 在 $8$ 中的因子补集是 $2 \cdot 2$.
\end{remark}
\end{frame}

\begin{frame}{Euler 函数}
 以 $\Phi_{m}$ 记“小于 $m$ 且与 $m$ 互素”的正整数集合， 即
 \[
   \Phi_{m}=\{a \mid(a, m)=1,1 \leqslant a<m\}.
 \]
 \pause
定理1说明， $\Phi_{m}$ 是 $(\mathbb{Z} / m \mathbb{Z})^{*}$ 的代表元集， 
$\Phi_{m}$ 称为\emph{模 $m$ 的最小正既约代表元系}， 简称\emph{既约系}。 
\pause
故 $(\mathbb{Z} / m \mathbb{Z}){ }^{*}$ 与 $\Phi_{m}$ 的元素个数相同， 记为 $\varphi(m)$, 即
 \[
 \varphi(m)=\#(\mathbb{Z} / m \mathbb{Z})^{*}=\# \Phi_{m}
 \]
 是 $\mathbb{Z} / m \mathbb{Z}$ 中的可逆元个数。 称 $\varphi$ 为 \emph{Euler 函数}。 %例如， $\varphi(1)=1$ (规定) $, \quad \varphi(2)=1, \quad \varphi(3)=2, \quad \varphi(4)=2, \quad \varphi(5)=4, \quad \varphi(6)=2$.

 \pause
 \begin{example}
$\varphi(1)=1$ (规定)。
\pause
 $(\mathbb{Z} / 2 \mathbb{Z})^{*}=\{\overline{1}\}$, $\varphi(2)=1$. 
 \pause
 $(\mathbb{Z} / 3 \mathbb{Z})^{*}=\{\overline{1},-\overline{1}\}$, $\varphi(3)=2$.
 \pause
 $(\mathbb{Z} / 4 \mathbb{Z})^{*}=\{\overline{1},-\overline{1}\}$, $\varphi(4)=2$.
 \pause
 $(\mathbb{Z} / 5 \mathbb{Z})^{*}=\{\overline{1}, \overline{2}, \overline{3}, \overline{4}\}$, $\varphi(5)=4$.
 \pause
 $(\mathbb{Z} / 8 \mathbb{Z})^{*}=\{\overline{1}, \overline{3}, \overline{5}, \overline{7}\}$, $\varphi(8)=4$.
 \end{example}

 \pause
 更一般地， 在 $(\mathbb{Z} / m \mathbb{Z})^*$ 中的每个同余类中取一个代表元得到的集合， 称为\emph{模 $m$ 的一个既约(代表元)系}(或\emph{既约剩余系}， 或缩系， reduced residue system). 
\pause
 例如， 模 $8$ 的既约剩余系可取为 $\{1,3,5,7\}$ 或 $\{1,-1,3,-3\}$. 
\pause
 $\Phi_{m}$ 是最常用的既约系。

 \end{frame}

 \begin{frame}

 \begin{lemma}%引理1
 (1) 任意 $\varphi(m)$ 个与 $m$ 互素的且模 $m$ 互不同余的正整数构成模 $m$的一个既约剩余系。

  (2) 设 $(u, m)=1$, 则整数集 $S$ 与 $u S=\{u s \mid s \in S\}$ 同时是或不是模 $m$ 的一个既约剩余系。 
  特别知， $u \Phi_{m}$ 是模 $m$ 的一个既约剩余系。
\end{lemma}
\pause
\begin{proof}
  (1) 显然这些整数代表的同余类不同，都属于 $(\mathbb{Z} / m \mathbb{Z})^{*}$ ，且与 $(\mathbb{Z} / m \mathbb{Z})^*$ 中同余类个数相同。

 (2) 若 $S$ 是模 $m$ 的一个既约剩余系，对互异的 $s_{1}, s_{2} \in S$, 必然
   $u s_{1} \nequiv us_{2} \quad \left(\mod m\right);$
 否则将导致 $s_{1} \equiv s_{2}\left(\mod m\right)$ (因为 $u$ 与 $m$ 互素), 从而 $s_{1}=s_{2}$. 
 故 $u S$ 是模 $m$ 互不同余的 $\varphi(m)$ 个与 $m$ 互素的正整数， 构成模 $m$ 的一个既约剩余系。 反之， 同理可证。
 \end{proof}

 \pause
   \begin{theorem}%定理2
     (1) $\varphi(m n)=\varphi(m) \varphi(n)$ (当 $m, n$ 为互素正整数).
     (此等式被简称为： $\varphi$ 是积性函数。注意我们规定了 $\varphi(1)=1$.)

     (2) 令$m>1$. 对Euler 函数 $\varphi(m)$ 的取值如下决定：
     若$m=p_{1}^{e_{1}} \cdots p_{s}^{e_{s}}$, 其中$p_{1}, \cdots, p_{s}$ 是两两不同的素数且$e_i>0$,
     则
     \[
       \varphi(m)=m(1-\frac{1}{p_1})\cdots(1-\frac{1}{p_s}).
       \]
       特别地，
 $\varphi\left(p^{e}\right)=p^{e-1}(p-1)$ (当 $p$ 为素数).
 \end{theorem}

 \end{frame}

 \begin{frame}
   如$\varphi(100)=\varphi(2^2\cdot 5^2)=100(1-\frac{1}{2})(1-\frac{1}{5})=40$.
      

   \pause
   \begin{proof}
   (1) 由下面的定理3我们将知道
   \[
     m\Phi_n+n\Phi_m=\{mx+ny\mid x\in \Phi_n, y\in \Phi_m\}
   \]
   满足\\
   (i) 对$(x,y)\neq (x', y')\in \Phi_n\times \Phi_m$, $mx+ny\neq mx'+ny'$;\\
   (ii) $m\Phi_n+n\Phi_m$构成模$mn$的一个既约代表元系。\\
   \pause
   这样
   \[
        \varphi(mn)= \sharp \left( m\Phi_n+n\Phi_m \right) = \varphi(n)\varphi(m).
   \]

   \pause
   (2) 我们先证明$m=p^e$的情形。
\pause
   “与 $p^{e}$ 不互素” 的正整数有 $p, 2 p, 3 p, \cdots, p^{e-1} \cdot p$, 共 $p^{e-1}$ 个。
\pause
   故“与 $p^{e}$ 互素而小于 $p^{e}$ ”的正整数个数为 $p^{e}-p^{e-1}$, 即 
   \[
     \varphi\left(p^{e}\right)=p^{e-1}(p-1)=p^e(1-\frac{1}{p}).
   \]
   \pause
   一般地，对$m=p_{1}^{e_{1}} \cdots p_{s}^{e_{s}}$由 $\varphi$的积性知
   \[
   \begin{aligned}
\varphi(m)&= \varphi(p_1^{e_1}) \cdots \varphi(p_s^{e_s})
\pause
      =p_1^{e_1}(1-\frac{1}{p_1})\cdots p_s^{e_1}(1-\frac{1}{p_s})
      \pause
      =   m (1-\frac{1}{p_1})\cdots(1-\frac{1}{p_s}).
         \end{aligned}
 \]
\end{proof}
 \end{frame}

 \begin{frame}
 
\begin{theorem}%定理3
设 $m, n$ 为互素正整数， 记 $m \Phi_{n}+n \Phi_{m}=\left\{m x+n y \mid x \in \Phi_{n}, y \in \Phi_{m}\right\}$, 则 
\[
  mx+ny\nequiv mx'+ny'\left( \mod mn \right), \quad\text{对$(x,y)\neq (x', y')\in \Phi_n\times \Phi_m$;}
\]
且
\begin{equation*}
  m \Phi_{n}+n \Phi_{m}\left( \mod mn \right) = \Phi_{m n} \left(\mod m n\right). \tag{1}
\end{equation*}
%(即两个集合的元素之间对应同余). 
也可叙述为：当 $x, y$ 分别遍历模 $n$ 和模 $m$ 的既约剩余系时， 
$m x+n y$ 恰好遍历模 $m n$ 的既约剩余系。
\end{theorem}

\pause 
\begin{proof}
  第一步： 令$(x,y)\neq (x', y')\in \Phi_n\times \Phi_m$.
  \pause
  若$x\neq x'$, 则$x\nequiv x'\left( \mod n \right)$, 从而
\[
  mx+ny\equiv mx \nequiv mx' \equiv mx'+ny'\left( \mod n \right).
\]
故由\S2.1定理1(7)知
\[
mx+ny\nequiv mx'+ny'\left( \mod mn \right).
\]
\pause
类似地，亦可从$y\neq y'$推出
\[
  mx+ny\nequiv mx'+ny'\left( \mod mn \right).
\]
\end{proof}


\end{frame}
 \begin{frame}

\begin{proof}[续]
 第二步：我们证明
 \[
   m \Phi_{n}+n \Phi_{m} \left( \mod mn \right) =  \Phi_{m n} \left(\mod m n\right).
 \]
 \pause
 既然$n$ 和 $y$ 均与 $m$ 互素，由\S1.2定理1%
 \footnote{\S1.2定理1可重述为：若$a\equiv r\left( \mod b \right)$, 则$(a,r)=(b,r)$.}
 知$(m x+n y, m)=(n y, m)=1$.
\pause
 同理 $(m x+n y, n)=1$.
 \pause
 故
 \[
   (m x+n y, m n)=1.
 \]
 \pause
 从而 (1)式左边属于右边：$m \Phi_{n}+n \Phi_{m}\left(\mod m n\right) \subset \Phi_{m n} \left(\mod m n\right)$.
 \pause
我们再证反过来的包含关系。
 \pause
 既然$n,m$互素，由引理 1, $n \Phi_{m}$ 也是模 $m$ 既约剩余系。
\pause
 任取 $a \in \Phi_{m n}$, 则 $a$ 与 $m$ 互素，故$\bar{a}\in n\Phi_{m}$, 即 $a$ 同余于 $n \Phi_{m}$ 中某元 $(\mod m)$, 设为 $a \equiv n y\left(\mod m\right), y \in \Phi_{m}$. 
\pause
   同理得
 \[
   a \equiv m x \quad(\mod n), \quad x \in \Phi_{n}.
 \]
 \pause
 故 $a \equiv m x+n y$ 对模 $m$ 和模 $n$ 都成立， 即知 $a \equiv m x+n y\left(\mod m n\right)$. 
\pause
 故 (1) 式右边集合中任一元 $a$ 必同余于左边集合中某元素。 
\pause
 综上知， 两边集合元素模 $m n$ 对应同余。
 \end{proof}


\end{frame}
 \begin{frame}

\begin{corollary}%系
$\sum_{d \mid m} \varphi(d)=m$ (求和遍历 $m$ 的正因子 $d$.)
\end{corollary}

\pause
\begin{proof*}[证法 1]
  %考虑 $m$ 个分数： $1 / m, 2 / m, \cdots,(m-1) / m, m / m$. 将它们皆约化为既约分数。 于是分母均为 $m$ 的因子。 考虑分母为 $d$ 的分数 $* / d$ 全体， 分子取遍与 $d$ 互素而不超过 $d$ 的所有正整数， 故这样的分数共 $\varphi(d)$ 个。 对各 $d \mid m$ 求和， 则得 $m$.
  令$S=\left\{ \frac{1}{m}, \frac{2}{m}, \cdots,\frac{m-1}{m}, \frac{m}{m} \right\}$.
  对$m$的正因子$d$, 令$S_d=\left\{ e/d\mid (e,d)=1, 1\leqslant e\leqslant d \right\}$;
  注意到$S_1=\left\{ 1 \right\}$, 而$d>1$时 $S_d=\Phi_d$.
  对$S$中每个分数约化为既约分数后可知其落在某个$S_d$中。
  进而易知$S$是这些$S_d$的无交并。
  故$m=\# S=\sum_{d\mid m}\# S_d=\sum_{d\mid m} \varphi(d)$.
\end{proof*}
%
%\pause
%\begin{proof*}[证法 2]
%  先设 $m=p^{e}$, 则其因子为 $d=p^{k}(0 \leqslant k \leqslant e)$, 而 $\varphi\left(p^{k}\right)=p^{k}-p^{k-1}$ (定理 2). 故
%\[
%\sum_{d \mid m} \varphi(d)=\sum_{0 \leqslant k \leqslant e} \varphi\left(p^{k}\right)=1+\sum_{1 \leqslant k \leqslant e}\left(p^{k}-p^{k-1}\right)=p^{e}
%\]
%再设 $m=p_{1}^{e_{1}} \cdots p_{s}^{e_{s}}$ 为其因子分解， 则因子 $d$ 可能为
%$p_{1}^{k_{1}} \cdots p_{s}^{k_{s}}$ $\left(0 \leqslant k_{i} \leqslant e_{i}, 1 \leqslant i \leqslant s\right)$.
%故由定理 2 知
%\[
%  \begin{aligned}
%  \sum_{d \mid m} \varphi(d) & =\sum_{k_{1}, \cdots, k_{s}} \varphi\left(p_{1}^{k_{1}} \cdots p_{s}^{k_{s}}\right)=\sum_{k_{1}, \cdots, k_{s}} \varphi\left(p_{1}^{k_{1}}\right) \cdots \varphi\left(p_{s}^{k_{s}}\right) \\
%& =\sum_{k_{1}} \varphi\left(p_{1}^{k_{1}}\right) \cdots \sum_{k_{s}} \varphi\left(p_{s}^{k_{s}}\right)=p_{1}^{e_{1}} \cdots p_{s}^{e_{s}}=m
%\end{aligned}
%\]
%\end{proof*}
%
%\begin{proof*}[证法 3]
%  固定 $d \mid m$, 考虑满足 $(a, m)=d$ 的整数 $a$ 的集合 $A_{d}$, 这当且仅当
%\[
%  (a / d, m / d)=1.
%\]
%故满足前式的 $a$ ($1 \leqslant a \leqslant m$) 是一一对应于满足后式的 $a_{1}=a / d$ ($1 \leqslant a_{1} \leqslant m / d$).
%而按 Euler 函数 $\varphi$ 的定义知， 后者个数为 $\varphi(m / d)$, 故$\#A_{d}=\varphi(m/d)$. 
%而任意 $a$ $(1 \leqslant a \leqslant m)$ 皆属于某个 $A_{d}$ (对某个 $\left.d \mid m\right)$. 故
%\[
%  m=\sum_{d \mid m} \# A_{d}=\sum_{d \mid m} \varphi(m / d).
%\]
%令 $\delta=m / d$, 则知后者即为 $\sum_{\delta \mid m} \varphi(\delta)$.
%\end{proof*}
%

\pause
现在回头看同余式约化性质：若 $(d, m)=1, d\mid a, d\mid b$, 则由 $a \equiv b\left(\mod m\right)$可得
\[
  a / d \equiv b / d \quad(\mod m).
\]
这是很自然的了， 因为此时 $d\left(\mod m\right)$ 可逆， 当然可约去了 (即 $\left.\bar{a} \bar{d}^{-1}=\bar{b} \bar{d}^{-1}\right)$.

\pause
\begin{corollary}[线性同余式， 线性同余方程]%系2
    考虑同余式:
    $a x \equiv b  \left(\mod m\right)$. 

(1) 如果 $(a, m)=1$, 则有唯一解 (模 $m$ 意义下).

 (2) 如果 $(a, m)=d>1$, 则当且仅当 $d \mid b$ 时有解。
且 有 $d$ 个 不同的解 (模 $m$ 的意义下)； 若$x_{0}$ 是任一解，则这$d$个解为
 \[
   x=x_0,\quad x_{0}+m_{1}, \quad \cdots, \quad x_{0}+(d-1) m_{1}\quad \left( \mod m \right).
 \] 
 \end{corollary}
\end{frame}


 \begin{frame}

 \begin{proof}
  (1) 如果 $(a, m)=1$, 则 $a(\mod m)$ 可逆， 两边同乘其逆， 就解出
\[
  x=b a^{-1} \quad(\mod m), \quad\text {即~} \bar{x}=\bar{b} \bar{a}^{-1}.
\]
自然解是唯一的 (模 $m$ 意义下， 即所有的解模 $m$ 同余), 因为 $\bar{a} \bar{x}_{0}=\bar{b}$ 导致 $\bar{x}_{0}=$ $\bar{b} \bar{a}^{-1}$ (求解方法：由辗转相除得 Bézout 等式 $u a+v m=1$, 则 $u a \equiv 1(\mod m)$, $b u a \equiv b(\mod m))$.

(2) 如果 $(a, m)=d>1$, 则有解时应 $d \mid b$ (因为 $b=a x+m k)$.
反过来，设 $d \mid b$. 令$a_{1}=\frac{a}{d}, b_{1}=\frac{b}{d}, m_{1}=\frac{m}{d}$.
容易发现：对整数$x_0$, $ax_0\equiv b\left( \mod m \right)$当且仅当$a_1x_0\equiv b_1\left( \mod m_1 \right)$;
换句话说，$ax\equiv b\left( \mod m \right)$与$a_1x\equiv b_1\left( \mod m_1 \right)$有相同的整数解。
注意到$(a_1,m_1)=1$, 由(1)知$a_1x\equiv b_1\left( \mod m_1 \right)$有 (模$m_1$意义下惟一) 解，
故$ax\equiv b\left( \mod m \right)$有解 (且在模$m_1$意义下惟一)。
这就证明了关于解的存在性的断言。

上一段的论证表明$ax\equiv b\left( \mod m \right)$有解时求解可归结到(1)的情形，通过解$a_1x\equiv b_1\left( \mod m_1 \right)$.
 由于$a_1x\equiv b_1\left( \mod m_1 \right)$的解在模 $m_{1}$ 意义下是惟一的，
 原方程$ax\equiv b\left( \mod m \right)$的解在模 $m_{1}$ 意义下唯一。
 令$x_0$是一个整数解，则所有整数解为$x_0+km_1$ ($k\in \ZZ$), 
 易知这些整数解模$m$的同余类有$d$个，
 一组代表元为$x_0, x_{0}+m_{1},  \cdots, x_{0}+(d-1) m_{1}$.
 \end{proof}

   \begin{example}
     我们解同余方程$6x\equiv 9\left( \mod 27 \right)$.
     \pause
     此时$a=6, m=27$, $d=(6,27)=3$, $m_1=m/d=9$.
     \pause
     从原方程消去$d=3$得方程$2x\equiv 3\left( \mod 9 \right)$.
     \pause
     由于$2\left( \mod 9 \right)$的逆为$5\left( \mod 9 \right)$,
     对该方程两边乘$5$得$x\equiv 15\equiv 6\left( \mod 9 \right)$.
     \pause
     故$x\equiv 6, 15, 24\left( \mod 27 \right)$.
   \end{example}
 \end{frame}

 \begin{frame}{小结}
   \begin{enumerate}
     \item 描述同余类环$\ZZ/m\ZZ$中的单位。
     \item 何时$\ZZ/m\ZZ$为域？
     \item 何为模$m$的既约（代表元）系？
     \item 何为Euler~$\varphi$ 函数？举例说明其值。
     \item 何为Euler函数的积性？有素因子分解时如何计算$\varphi(n)$?
     \item 说说你知道的关于Euler~$\varphi$函数的其他结论。多多益善。
     \item 同余方程$ax\equiv b\left( \mod m \right)$的解的存在性、求解、解集如何？
   \end{enumerate}
 \end{frame}
